#include <bits/stdc++.h>

using namespace std;

int n;
long f[1000010];   // 用于保存Pell数列
long a[1000010] = {0}; // 用于保存输入的数
int main() {
    f[1] =1,f[2] = 2;

    // 计算Pell数列
    for(long i = 3;i <= 1000010;i++) {
        f[i] = (2 * f[i - 1] % 32767 + f[i - 2] % 32767) % 32767;
    }

    // 保存所有的输入
    int n;
    cin >> n;
    for(int i = 0;i < n;i++) {
        cin >> a[i];
    }

    // 输出结果
    for (int i = 0;i < n;i++) {
        cout << f[a[i]] << endl;
    }




}